/* Copyright 2012 Tobias Marschall
 *
 * This file is part of CLEVER.
 *
 * CLEVER is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * CLEVER is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with CLEVER.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <iostream>
#include <algorithm>
#include <cassert>

#include "OverlappingRegions.h"

using namespace std;

OverlappingRegions::OverlappingRegions() {
	changed = false;
}

OverlappingRegions::~OverlappingRegions() {
}

void OverlappingRegions::add(int chromosome_id, int start, int end) {
	assert(start <= end);
	events.push_back(event_t(chromosome_id, start, START));
	events.push_back(event_t(chromosome_id, end + 1, END));
	changed = true;
}

void OverlappingRegions::add(const OverlappingRegions& regions) {
	for (size_t i = 0; i < regions.events.size(); ++i) {
		events.push_back(regions.events[i]);
	}
	changed = true;
}

void OverlappingRegions::subtract(const OverlappingRegions& regions) {
	// if substracted from itself, the result is the empty set
	if (&regions == this) {
		events.clear();
		changed = true;
		return;
	}
	for (size_t i = 0; i < regions.events.size(); ++i) {
		const event_t& e = regions.events[i];
		switch (e.type) {
			case START:
				events.push_back(event_t(e.chromosome_id, e.pos, START_EXCLUDED));
				break;
			case END: 
				events.push_back(event_t(e.chromosome_id, e.pos, END_EXCLUDED));
				break;
			default:
				assert(false);
		}
	}
	changed = true;
	condense();
}

void OverlappingRegions::condense() const {
	if (!changed) return;
	sort(events.begin(), events.end(), event_comparator_t());
	disjoint_intervals.clear();
	int active = 0;
	int active_excluded = 0;
	int start = 0;
	int chromosome_id = -1;
	for (size_t i=0; i<events.size(); ++i) {
		const event_t& e = events[i];
		switch (e.type) {
		case START:
			if ((active == 0) && (active_excluded == 0)) {
				chromosome_id = e.chromosome_id;
			} else {
				assert(chromosome_id == e.chromosome_id);
			}
			if (active == 0) {
				start = e.pos;
			}
			active += 1;
			break;
		case END:
			active -= 1;
			assert(active >= 0);
			assert(chromosome_id == e.chromosome_id);
			if ((active == 0) && (active_excluded == 0)) {
				disjoint_intervals.push_back(interval_t(chromosome_id, start, e.pos - 1));
			}
			break;
		case START_EXCLUDED:
			if ((active == 0) && (active_excluded == 0)) {
				chromosome_id = e.chromosome_id;
			} else {
				assert(chromosome_id == e.chromosome_id);
			}
			active_excluded += 1;
			if ((active > 0) && (active_excluded == 1) && (start < e.pos)) {
				disjoint_intervals.push_back(interval_t(chromosome_id, start, e.pos - 1));
			}
			break;
		case END_EXCLUDED:
			active_excluded -= 1;
			assert(active_excluded >= 0);
			assert(chromosome_id == e.chromosome_id);
			if (active > 0) {
				start = e.pos;
			}
			break;
		default:
			assert(false);
		}
	}
	events.clear();
	vector<OverlappingRegions::interval_t>::const_iterator it = disjoint_intervals.begin();
	for (; it != disjoint_intervals.end(); ++it) {
		events.push_back(event_t(it->chromosome_id, it->start, START));
		events.push_back(event_t(it->chromosome_id, it->end + 1, END));
	}
	changed = false;
}

const vector<OverlappingRegions::interval_t>& OverlappingRegions::list() const {
	condense();
	return disjoint_intervals;
}

bool OverlappingRegions::overlapsWith(int chromosome_id, int start, int end) const {
	condense();
	cerr << "OverlappingRegions::overlapsWith(" << chromosome_id << ", " << start << ", " << end << ')' << endl;
	// binary search to find first event before given interval
	event_comparator_endfirst_t smaller;
	event_t start_event(chromosome_id, start, START);
	event_t end_event(chromosome_id, end+1, END);
	int i = events.size() / 2;
	while (true) {
		assert(i >= 0);
		assert(i < events.size());
		cerr << "i=" << i << ", events[i]=" << events[i] << ", events[i+1]=";
		if (i+1 < events.size()) cerr << events[i+1] << endl;
		else cerr << "None" << endl;
		if (!smaller(start_event, events[i])) {
			if (i + 1 == events.size()) break;
			if (smaller(start_event, events[i+1])) break;
			i = (i + events.size()) / 2;
		} else {
			if (i == 0) {
				i = -1;
				break;
			}
			i = i / 2;
		}
	}
	cerr << "Index before: " << i << endl;
	if (i >= 0) {
		if (events[i].type == START) {
			assert(events[i].chromosome_id == chromosome_id);
			return true;
		}
	}
	i += 1;
	if ((i < events.size()) && (smaller(events[i],end_event))) {
		assert(events[i].type == START);
		return true;
	}
	return false;
}

std::ostream& operator<<(std::ostream& os, const OverlappingRegions& regions) {
	const vector<OverlappingRegions::interval_t>& intervals = regions.list();
	vector<OverlappingRegions::interval_t>::const_iterator it = intervals.begin();
	for (; it != intervals.end(); ++it) {
		if (it != intervals.begin()) os << ",  ";
		os << "[" << it->chromosome_id << "," << it->start << ":" << it->end << "]";
	}
	return os;
}

ostream& operator<<(std::ostream& os, const vector<OverlappingRegions::event_t>& events) {
	os << "(events: ";
	for (size_t i=0; i<events.size(); ++i) {
		if (i>0) os << "; ";
		os << events[i].chromosome_id << "," << events[i].pos << "," << events[i].type;
	}
	os << ')';
	return os;
}

std::ostream& operator<<(std::ostream& os, const OverlappingRegions::event_t& e) {
	os << '(' << e.chromosome_id << ',' << e.pos << ',' << e.type << ')';
	return os;
}
